package MySQL::Query::OrderOfExecution;

use strict;
#use warnings;
use Carp;
use Data::Dumper;
use Algorithm::Combinatorics qw(permutations partitions );
use SQL::Builder::Join;
use Storable qw (dclone);
use Graph;

use base qw(MySQL::Query::Base);
__PACKAGE__->mk_accessors(qw( tables ));

sub graph {
      my ($self , $sql) = @_;
        
      my $copy = dclone($sql);
        
      my $graph = Graph->new();
      my $list = $copy->tables->joins->list;
        
      for (my $i = 0; $i <= $#{$list}; $i++) {
            my $join = $copy->tables->joins->list->[$i];
                
            my $left = $join->left_table;
            my $right = $join->right_table;
            my $type = $join->type;
                
            if ($type =~ /LEFT|RIGHT/) {
                  if (!$left) {
                        $left = $list->[$i - 1]->right_table; 
                        $graph->add_path($left , $right);
                        $graph->set_attribute('strong_out', $left , '1');
                        $graph->set_attribute('strong_in', $right , '1');
                        $graph->set_attribute('join_type' , $right , $type);
                  } else {
                        $graph->add_path($right , $left);
                        $graph->set_attribute('strong_out', $right , '1');
                        $graph->set_attribute('strong_in', $left , '1');
                        $graph->set_attribute('join_type' , $left , $type);
                  }
            } else {
                  $graph->add_vertex($left) if $left;
                  $graph->add_vertex($right) if $right;
            }
      }
        
      my @vertices = $graph->vertices;
      for (my $i = 0; $i <= $#vertices; $i++) {
            my $start_point = $vertices[$i];
            my $sp_strong_in = $graph->has_attribute('strong_in' , $start_point);
            my $sp_strong_out = $graph->has_attribute('strong_out' , $start_point);
                
            for (my $j = 0; $j <= $#vertices; $j++) {
                  my $next_point = $vertices[$j];
                  my $np_strong_in = $graph->has_attribute('strong_in' , $next_point);
                  my $np_strong_out = $graph->has_attribute('strong_out' , $next_point);
                        
                  next if ($sp_strong_in and $np_strong_out);
                  next if ($sp_strong_out and $np_strong_in);
                  next if ($start_point eq $next_point);
                  next if ($graph->has_path($start_point , $next_point));
                        
                  $graph->add_path($start_point , $next_point);
            }
      }
        
      for (my $i = 0; $i <= $#vertices; $i++) {
            my $start_point = $vertices[$i];
            next if $graph->has_attribute('strong_in' , $start_point);
                
            my @s = $graph->neighbors($start_point);
            use Data::Dumper;
            print Dumper \@s;
      }
        
      # graph should be built corretly at that moment
      # now we should find the path
      print $graph;
}


sub orders {
      my ($self , $sql , $tables_o) = @_;
        
      #the following code is a total mystery
      #graph() should be used instead,, when it's ready
      die "sql param should be SQL::Builder::Select object, not a plain sql. Query::Tree::as_builder to rescue\n"
            unless ($sql->isa('SQL::Builder::Select'));
      die "Tables object expected (Query::Tables.pm)\n"
            unless $tables_o;
      $self->tables($tables_o);
        
      my $copy = dclone($sql);
      my @variants = ();
        
      if (@{$copy->tables->tables->list}) {
            my $dif_sql = $self->reorder_sql($copy);
            @variants = @$dif_sql;
      } else {
            unless ($#{$copy->tables->joins->list}) { # t1 JOIN t2
                  my $v = $self->reorder_two($copy);
                  push @variants , $v if $v;
                  push @variants , $sql->sql;
            } else { 
                  my $tables = $self->get_used_tables($copy);
                  my $map = $self->build_orders_map($copy);
                  
                  my @pass = ();
                  my $all_variants = $self->all_possible($tables);
                        
                  my $pass_variants = $self->apply_orders_map($map , $all_variants);      
                  
                  #my $all_tables = $self->tables->tables; #tables and joins are different
                  
                  for (my $i = 0; $i <= $#{$pass_variants}; $i++) {
                        $self->create_first_join($sql , $copy , $pass_variants->[$i] , $tables);
                        $self->create_next_join($sql , $copy , $pass_variants->[$i] , $tables);
                        
                        push @variants , $copy->sql;
                  }
            }
      }          
      
      return \@variants;
}

sub list_orders {
      my ($self , $tables) = @_;
      
      my @orders = permutations($tables);
      return \@orders;
}

sub reorder_sql {
      my ($self , $sql_obj) = @_;
      
      my $orders = $self->list_orders($sql_obj->tables->tables->list);
            
      my @variants = ();
      for (@$orders) {
            $sql_obj->tables->tables->list_clear;
            $sql_obj->tables->tables->list_push(@$_);
            push @variants , $sql_obj->sql;
      }
      return \@variants;
}

sub reorder_two {
      my ($self , $sql_obj) = @_;
      
      my $join = $sql_obj->tables->joins->list->[0];
      my $type = $join->type;
      
      unless ($type =~ /^(LEFT|RIGHT)/) {
            my $left_table = $join->left_table;
            my $right_table = $join->right_table;
                  
            $join->left_table($right_table);
            $join->right_table($left_table);
                  
            $sql_obj->tables->joins->list_clear;
            $sql_obj->tables->joins->list_push($join);
            
            return $sql_obj->sql;
      }
}

sub get_used_tables {
      my ($self , $sql_obj) = @_;
      
      my @tables = ();
      for (my $i = 0; $i <= $#{$sql_obj->tables->joins->list}; $i++) {
            my $current_join = $sql_obj->tables->joins->list->[$i];
            my $left_table = $current_join->left_table;
            my $right_table = $current_join->right_table;
            
            my $left_alias = $current_join->left_alias;
            my $right_alias = $current_join->right_alias;
            
            unless ($left_table) {
		  $left_table = $sql_obj->tables->joins->list->[$i - 1]->right_table;
                  $left_alias = $sql_obj->tables->joins->list->[$i - 1]->right_alias;
	    }
	    
	    my $left_side = $left_alias || $left_table;
	    my $right_side = $right_alias || $right_table;
	
            push @tables , ($left_side , $right_side);
      }
      
      my %see = ();
      @tables = grep { $_ && !$see{$_}++ } @tables;
            
      return \@tables;
}

sub build_orders_map {
      my ($self , $sql_obj) = @_;
      
      my %map = ();
      
      for (my $i = 0; $i <= $#{$sql_obj->tables->joins->list}; $i++) {
            my $current_join = $sql_obj->tables->joins->list->[$i];
            my $left_table = $current_join->left_table;
            my $right_table = $current_join->right_table;
            
            my $left_alias = $current_join->left_alias;
            my $right_alias = $current_join->right_alias;
            
            unless ($left_table) {
		  $left_table = $sql_obj->tables->joins->list->[$i - 1]->right_table;
                  $left_alias = $sql_obj->tables->joins->list->[$i - 1]->right_alias;
	    }
	    
	    my $left_side = $left_alias || $left_table;
	    my $right_side = $right_alias || $right_table;
	
            if ($current_join->type =~ /^(LEFT|RIGHT)/) {
                  push @{$map{$left_side}} , $right_side;
            }
      }
      
      return \%map;
}

sub apply_orders_map {
      my ($self , $map , $variants) = @_;
      
      my @pass = ();
      TOP: for (my $i = 0; $i <= $#{$variants}; $i++) {
            for (my $j = 0; $j <= $#{$variants->[$i]}; $j++) {
                  next unless exists $map->{$variants->[$i]->[$j]};
                  
                  my @t1;
                  for (my $h = $j; $h <= $#{$variants->[$i]}; $h++) {
                        push @t1 , $variants->[$i]->[$h];        
                  }
                  
                  my @t2 = @{$map->{$variants->[$i]->[$j]}};
                  next TOP unless $self->in_array_comp(\@t1 , \@t2);
            }
            push @pass , $variants->[$i];
      }
      return \@pass;
}

sub create_first_join {
      my ($self , $original_sql , $sql_obj , $order , $tables) = @_;
      
      $sql_obj->tables->joins->list_clear;
      for (my $i = 0; $i <= $#{$order}; $i++) {
            my $join = SQL::Builder::Join->new();
            if (grep { $_ eq $order->[$i] } @$tables) {
                  $join->left_table($order->[$i]);
            } else {
                  my $table = $self->tables->table_by_alias($order->[$i]);
                  $join->left_table($table);
                  $join->left_alias($order->[$i]);
            }
            
            ++$i;
	
            if (grep { $_ eq $order->[$i] } @$tables) {
                  $join->right_table($order->[$i]);
            } else {
                  my $table = $self->tables->table_by_alias($order->[$i]);
                  $join->right_table($table);
                  $join->right_alias($order->[$i]);
            }
            
            for my $m (@{$original_sql->tables->joins->list}) { #how are they connected?
                  if ($join->right_table and $m->right_table and
		      $m->right_table eq $join->right_table
		  ) {
                        $join->on($m->on);
                        $join->type($m->type);
                  } elsif ($m->left_table eq $join->right_table) {
                        $join->on($m->on);
                        #$join->type($m->type);
                  }
            }
            
            $sql_obj->tables->joins->list_push($join);
            
            last;
      }
}

sub create_next_join {
      my ($self , $original_sql , $sql_obj , $order , $tables) = @_;
      
      for (my $i = 2; $i <= $#{$order}; $i++) {
            my $join = SQL::Builder::Join->new();
            if (grep { $_ eq $order->[$i] } @$tables) {
                  $join->right_table($order->[$i]);
            } else {
                  my $table = $self->tables->table_by_alias($order->[$i]);
                  $join->right_table($table);
                  $join->right_alias($order->[$i]);
            }
            
            for my $m (@{$original_sql->tables->joins->list}) { #how are they connected?
                  if ($join->right_table and $m->right_table and
		      $m->right_table eq $join->right_table
		  ) {
                        $join->on($m->on);
                        $join->type($m->type);
                  } elsif ($m->left_table eq $join->right_table) {
                        $join->on($m->on);
                        #$join->type($m->type);
                  }
            }
            
            $sql_obj->tables->joins->list_push($join);
      }
}

sub order {
      my ($self , $explain_ref) = @_;
	
      my @tables = ();
      for my $table (@{$explain_ref}) {
	    push @tables , $table->{table};
      }
      return @tables;
}

sub all_possible {
      my ($self , $tables) = @_;
      my @all_permutations = permutations($tables);
      return \@all_permutations;
}

sub indexes_comb {
      my ($self , $indexes) = @_;
       
      my @res = ();
      my @keys = keys %$indexes;
      
      #1. one index for each table
      foreach my $table (@keys) {
            push @res , { $table => $_ } foreach @{$indexes->{$table}};
      }
      
      #2. 
      
      #use Data::Dumper;
      #print Dumper $indexes;
      #die;
      
      #my $comb = partitions(\@keys);
      
      #print Dumper $comb;
      #die;
      
      #foreach
      
        
      
        
      return \@res;
}

sub comp {
      my ($self , $tables1_ref , $tables2_ref) = @_;
	
      return 0 if ($#{$tables1_ref} ne $#{$tables2_ref});
	
      for (my $i = 0; $i <= $#{$tables1_ref}; $i++) {
	    return 0 if $tables1_ref->[$i] ne $tables2_ref->[$i];
      }
	
      return 1;
}

sub in_array_comp {
      my ($self , $a1_ref , $a2_ref) = @_;
        
      my %seen = ();                 
      my $num = 0;
      
      @seen{@$a2_ref} = ();
      foreach my $item (@$a1_ref) {
            $num++ unless exists $seen{$item};
      }
        
      return 1 if ($num eq ($#{$a1_ref} - $#{$a2_ref}));
}

1;

=head1 NAME

MySQL::Query::OrderOfExecution

=head1 SYNOPSIS
	
=head1 DESCRIPTION

=head1 METHODS

=head2 new()

=head2 order()

=head2 comp()
